'lintcode 水果成篮'

Posted on | In

描述

在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：

把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。

你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果总量是多少

样例

示例 1:

输入: [1,2,1]
输出: 3
解释: 我们可以收集 [1,2,1].
示例 2:

输入: [1,2,3,2,2]
输出: 4
解释: 我们可以收集 [2,3,2,2].
如果我们从第一棵树开始，我们将只能收集到 [1, 2].

思考

设置两个指针left和right，初始状态left = 0， right = 1， right右边这个水果如果和现在篮子中的水果一样，那么总数就加一，如果不一样就更改left和right指针。
这里要注意两个问题：

  1. 有可能初始时篮框里面放的是一样的水果，这里需要加一个判断。
  2. 更改left指针的时候，left不一定更改到现在的right处，要找到最左边的一样的水果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    /**
     * @param tree: The type of fruit
     * @return: The total amount of fruit you can collect.
     */
    int totalFruit(vector<int> &tree) {
        // write your code here
        if (tree.size() == 1 || tree.size() == 2)
            return tree.size();
        int res = 2;
        int m = 1;
        int left = 0, right = 1;
        vector<int> temp(2,0);
        temp[0] = tree[left];
        temp[1] = tree[right];
        while (right < tree.size() - 1) {
            if (tree[right+1] == temp[0] || tree[right+1] == temp[1]) {
                right++;
                res++;
                m = max(m, res);
            }
            else {
                if (temp[0] == temp[1]) {
                    temp[1] = tree[right+1];
                    res++;
                    right++;
                    m = max(m,res);
                }
                else {
                    left = right;
                    res = 2;
                    while (tree[left] == tree[left-1]) {
                        left--;
                        res++;
                    }
                    right++;
                    temp[0] = tree[left];
                    temp[1] = tree[right];

                }
            }
        }
        return m;
    }
};
-------------end of filethanks for reading-------------